翻訳と辞書 Words near each other ・ Star of Artaban ・ Star of Asia ・ Star of Bethlehem ・ Star of Bethlehem (disambiguation) ・ Star of Bethlehem (painting) ・ Star of Bombay ・ Star of Caledonia ・ Star of Courage ・ Star Hall ・ Star Harbor, Texas ・ Star Hawkins ・ Star Hawks ・ Star Healer ・ Star Health and Allied Insurance ・ Star height ・ Star height problem ・ Star Hellas ・ Star Hero ・ Star Hill AME Church ・ Star Historic District ・ Star hopping ・ Star Horn Royal Club ・ Star Hotel ・ Star Hotel riot ・ Star Hotel, Balmain ・ Star Hotel, Great Yarmouth ・ Star Hotshots ・ Star Hotshots all-time roster ・ Star House ・ Star Hunter Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Star height problem ： ウィキペディア英語版 Star height problem The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was raised by . ==Families of regular languages with unbounded star height== The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height ''n'' for every ''n''. Here, the star height ''h''(''L'') of a regular language ''L'' is defined as the minimum star height among all regular expressions representing ''L''. The first few languages found by are described in the following, by means of giving a regular expression for each language: :$\backslash begin$ e_1 &= a_1^ * \\ e_2 &= \left(a_1^ *a_2^ *a_3\right)^ *\\ e_3 &= \left(\left(a_1^ *a_2^ *a_3\right)^ *\left(a_4^ *a_5^ *a_6\right)^ *a_7\right)^ *\\ e_4 &= \left( \left(\left(a_1^ *a_2^ *a_3\right)^ *\left(a_4^ *a_5^ *a_6\right)^ *a_7\right)^ * \left(\left(a_8^ *a_9^ *a_\right)^ *\left(a_^ *a_^ *a_\right)^ *a_\right)^ * a_\right)^ * \end The construction principle for these expressions is that expression $e\_$ is obtained by concatenating two copies of $e\_n$, appropriately renaming the letters of the second copy using fresh alphabet symbols, concatenating the result with another fresh alphabet symbol, and then by surrounding the resulting expression with a Kleene star. The remaining, more difficult part, is to prove that for $e\_n$ there is no equivalent regular expression of star height less than ''n''; a proof is given in . However, Eggan's examples use a large alphabet, of size 2''n''-1 for the language with star height ''n''. He thus asked whether we can also find examples over binary alphabets. This was proved to be true shortly afterwards by . Their examples can be described by an inductively defined family of regular expressions over the binary alphabet $\backslash$ as follows–cf. : :$\backslash begin$ e_1 & = (ab)^ * \\ e_2 & = \left(aa(ab)^ *bb(ab)^ *\right)^ * \\ e_3 & = \left(aaaa \left(aa(ab)^ *bb(ab)^ *\right)^ * bbbb \left(aa(ab)^ *bb(ab)^ *\right)^ *\right)^ * \\ \, & \cdots \\ e_ & = (\,\underbrace_\, \cdot \, e_n\, \cdot\, \underbrace_\, \cdot\, e_n \,)^ * \end Again, a rigorous proof is needed for the fact that $e\_n$ does not admit an equivalent regular expression of lower star height. Proofs are given by and by . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Star height problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.